home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / CODECS.ZIP / codecs / english / codhuff.c next >
Encoding:
C/C++ Source or Header  |  1995-10-13  |  14.0 KB  |  359 lines
  1. /* File: codhuff.c
  2.    Author: David Bourgin (David.Bourgin@ufrima.imag.fr)
  3.    Creation date: 7/2/94
  4.    Last update: 24/7/95
  5.    Purpose: Example of Huffman encoding with a file source to compress.
  6.    Attention: The compiler must have been configured for a stack of at least
  7.    20 kb.
  8. */
  9.  
  10. #include <stdio.h>
  11. /* For routines fgetc,fputc,fwrite and rewind */
  12. #include <memory.h>
  13. /* For routines memset,memcpy */
  14. #include <malloc.h>
  15. /* For routines malloc and free */
  16. #include <stdlib.h>
  17. /* For routines qsort et exit */
  18.  
  19. /* Error codes returned to the caller */
  20. #define NO_ERROR      0
  21. #define BAD_FILE_NAME 1
  22. #define BAD_ARGUMENT  2
  23. #define BAD_MEM_ALLOC 3
  24.  
  25. /* Useful constants */
  26. #define FALSE 0
  27. #define TRUE  1
  28.  
  29. /* Global variables */
  30. FILE *source_file,*dest_file;
  31.  
  32. typedef struct s_tree { unsigned int byte;
  33.                              /* A byte has to be coded as an unsigned integer to allow a node to have a value over 255 */
  34.                         unsigned long int weight;
  35.                         struct s_tree *left_ptr,
  36.                                       *right_ptr;
  37.                       } t_tree,*p_tree;
  38. #define BYTE_OF_TREE(ptr_tree)  ((*(ptr_tree)).byte)
  39. #define WEIGHT_OF_TREE(ptr_tree)  ((*(ptr_tree)).weight)
  40. #define LEFTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).left_ptr)
  41. #define RIGHTPTR_OF_TREE(ptr_tree)  ((*(ptr_tree)).right_ptr)
  42.  
  43. typedef struct { unsigned char bits[32];
  44.                  unsigned int bits_nb;
  45.                } t_bin_val;
  46. #define BITS_BIN_VAL(bin_val)  ((bin_val).bits)
  47. #define BITS_NB_BIN_VAL(bin_val)  ((bin_val).bits_nb)
  48.  
  49.                              /* Being that fgetc=EOF only after any access
  50.                                 then 'stored_byte_status' is 'TRUE' if a byte has been stored with 'fgetc'
  51.                                 or 'FALSE' if there's no valid byte not already read and not handled in 'stored_byte_val' */
  52. int stored_byte_status=FALSE;
  53. int stored_byte_val;
  54.  
  55. /* Pseudo procedures */
  56. #define beginning_of_data()  { (void)rewind(source_file); stored_byte_status=FALSE; }
  57. #define end_of_data()  (stored_byte_status?FALSE:!(stored_byte_status=((stored_byte_val=fgetc(source_file))!=EOF)))
  58. #define read_byte()  (stored_byte_status?stored_byte_status=FALSE,(unsigned char)stored_byte_val:(unsigned char)fgetc(source_file))
  59. #define write_byte(byte)  ((void)fputc((byte),dest_file))
  60.  
  61. unsigned char bit_counter_to_write=0;
  62. unsigned int val_to_write=0;
  63.  
  64. void write_bin_val(bin_val)
  65. /* Returned parameters: None
  66.    Action: Writes in the output stream the value binary-coded into 'bin_val'
  67.    Errors: An input/output error could disturb the running of the program
  68. */
  69. t_bin_val bin_val;
  70. { unsigned char bin_pos,
  71.                 byte_pos;
  72.  
  73.   byte_pos=(BITS_NB_BIN_VAL(bin_val)+7) >> 3;
  74.   bin_pos=BITS_NB_BIN_VAL(bin_val) & 7;
  75.   if (bin_pos)
  76.      { byte_pos--;
  77.        val_to_write=(val_to_write<<bin_pos)|BITS_BIN_VAL(bin_val)[byte_pos];
  78.        bit_counter_to_write += bin_pos;
  79.        if (bit_counter_to_write>=8)
  80.           { bit_counter_to_write -= 8;
  81.             write_byte((unsigned char)(val_to_write>>bit_counter_to_write));
  82.             val_to_write &= ((1<<bit_counter_to_write)-1);
  83.           }
  84.      }
  85.   while (byte_pos)
  86.         { byte_pos--;
  87.           val_to_write=(val_to_write<<8)|BITS_BIN_VAL(bin_val)[byte_pos];
  88.           write_byte((unsigned char)(val_to_write>>bit_counter_to_write));
  89.           val_to_write &= ((1<<bit_counter_to_write)-1);
  90.         }
  91. }
  92.  
  93. void fill_encoding()
  94. /* Returned parameters: None
  95.    Action: Fills the last byte to write in the output stream with zero values
  96.    Errors: An input/output error could disturb the running of the program
  97. */
  98. { if (bit_counter_to_write)
  99.      write_byte(val_to_write << (8-bit_counter_to_write));
  100. }
  101.  
  102. void write_header(codes_table)
  103. /* Returned parameters: None
  104.    Action: Writes the header in the stream of codes
  105.    Errors: An input/output error could disturb the running of the program
  106. */
  107. t_bin_val codes_table[257];
  108. { register unsigned int i,j;
  109.   t_bin_val bin_val_to_0,
  110.             bin_val_to_1,
  111.             bin_val;         /* Is used to send in binary mode via write_bin_val */
  112.  
  113.   *BITS_BIN_VAL(bin_val_to_0)=0;
  114.   BITS_NB_BIN_VAL(bin_val_to_0)=1;
  115.   *BITS_BIN_VAL(bin_val_to_1)=1;
  116.   BITS_NB_BIN_VAL(bin_val_to_1)=1;
  117.   for (i=0,j=0;j<=255;j++)
  118.       if BITS_NB_BIN_VAL(codes_table[j])
  119.          i++;
  120.                              /* From there, i contains the number of bytes of the several non null occurrences to encode */
  121.                               /* First part of the header: Specifies the bytes that appear in the source of encoding */
  122.   if (i<32)
  123.      {                       /* Encoding of the appeared bytes with a block of bytes */
  124.        write_bin_val(bin_val_to_0);
  125.        BITS_NB_BIN_VAL(bin_val)=5;
  126.        *BITS_BIN_VAL(bin_val)=(unsigned char)(i-1);
  127.        write_bin_val(bin_val);
  128.        BITS_NB_BIN_VAL(bin_val)=8;
  129.        for (j=0;j<=255;j++)
  130.            if BITS_NB_BIN_VAL(codes_table[j])
  131.               { *BITS_BIN_VAL(bin_val)=(unsigned char)j;
  132.                 write_bin_val(bin_val);
  133.               }
  134.      }
  135.   else {                     /* Encoding of the appeared bytes with a block of bits */
  136.          write_bin_val(bin_val_to_1);
  137.          for (j=0;j<=255;j++)
  138.              if BITS_NB_BIN_VAL(codes_table[j])
  139.                 write_bin_val(bin_val_to_1);
  140.              else write_bin_val(bin_val_to_0);
  141.      };
  142.                              /* Second part of the header: Specifies the encoding of the bytes (fictive or not) that appear in the source of encoding */
  143.   for (i=0;i<=256;i++)
  144.       if (j=BITS_NB_BIN_VAL(codes_table[i]))
  145.          { if (j<33)
  146.               { write_bin_val(bin_val_to_0);
  147.                 BITS_NB_BIN_VAL(bin_val)=5;
  148.               }
  149.            else { write_bin_val(bin_val_to_1);
  150.                   BITS_NB_BIN_VAL(bin_val)=8;
  151.                 }
  152.            *BITS_BIN_VAL(bin_val)=(unsigned char)(j-1);
  153.            write_bin_val(bin_val);
  154.            write_bin_val(codes_table[i]);
  155.          }
  156. }
  157.  
  158. int weight_tree_comp(tree1,tree2)
  159. /* Returned parameters: Returns a comparison status
  160.    Action: Returns a negative, zero or positive integer depending on the weight
  161.    of 'tree2' is less than, equal to, or greater than the weight of 'tree1'
  162.    Errors: None
  163. */
  164. p_tree *tree1,*tree2;
  165. { return (WEIGHT_OF_TREE(*tree2) ^ WEIGHT_OF_TREE(*tree1))?((WEIGHT_OF_TREE(*tree2)<WEIGHT_OF_TREE(*tree1))?-1:1):0;
  166. }
  167.  
  168. void suppress_tree(tree)
  169. /* Returned parameters: None
  170.    Action: Suppresses the allocated memory for the 'tree'
  171.    Errors: None if the tree has been build with dynamical allocations!
  172. */
  173. p_tree tree;
  174. { if (tree!=NULL)
  175.      { suppress_tree(LEFTPTR_OF_TREE(tree));
  176.        suppress_tree(RIGHTPTR_OF_TREE(tree));
  177.        free(tree);
  178.      }
  179. }
  180.  
  181. p_tree build_tree_encoding()
  182. /* Returned parameters: Returns a tree of encoding
  183.    Action: Generates an Huffman encoding tree based on the data from the stream to compress
  184.    Errors: If no memory is available for the allocations then a 'BAD_MEM_ALLOC' exception is raised
  185. */
  186. { register unsigned int i;
  187.   p_tree occurrences_table[257],
  188.          ptr_fictive_tree;
  189.  
  190.                              /* Sets up the occurrences number of all bytes to 0 */
  191.   for (i=0;i<=256;i++)
  192.       { if ((occurrences_table[i]=(p_tree)malloc(sizeof(t_tree)))==NULL)
  193.            { for (;i;i--)
  194.                  free(occurrences_table[i-1]);
  195.              exit(BAD_MEM_ALLOC);
  196.            }
  197.         BYTE_OF_TREE(occurrences_table[i])=i;
  198.         WEIGHT_OF_TREE(occurrences_table[i])=0;
  199.         LEFTPTR_OF_TREE(occurrences_table[i])=NULL;
  200.         RIGHTPTR_OF_TREE(occurrences_table[i])=NULL;
  201.       }
  202.                              /* Valids the occurrences of 'occurrences_table' with regard to the data to compressr */
  203.   if (!end_of_data())
  204.      { while (!end_of_data())
  205.              { i=read_byte();
  206.                WEIGHT_OF_TREE(occurrences_table[i])++;
  207.              }
  208.        WEIGHT_OF_TREE(occurrences_table[256])=1;
  209.                              /* Sorts the occurrences table depending on the weight of each character */
  210.        (void)qsort(occurrences_table,257,sizeof(p_tree),weight_tree_comp);
  211.        for (i=256;(i!=0)&&(!WEIGHT_OF_TREE(occurrences_table[i]));i--)
  212.            free(occurrences_table[i]);
  213.        i++;
  214.                              /* From there, 'i' gives the number of different bytes with a null occurrence in the stream to compress */
  215.        while (i>0)           /* Looks up (i+1)/2 times the occurrence table to link the nodes in an uniq tree */
  216.              { if ((ptr_fictive_tree=(p_tree)malloc(sizeof(t_tree)))==NULL)
  217.                   { for (i=0;i<=256;i++)
  218.                         suppress_tree(occurrences_table[i]);
  219.                     exit(BAD_MEM_ALLOC);
  220.                   }
  221.                BYTE_OF_TREE(ptr_fictive_tree)=257;
  222.                WEIGHT_OF_TREE(ptr_fictive_tree)=WEIGHT_OF_TREE(occurrences_table[--i]);
  223.                LEFTPTR_OF_TREE(ptr_fictive_tree)=occurrences_table[i];
  224.                if (i)
  225.                   { i--;
  226.                     WEIGHT_OF_TREE(ptr_fictive_tree) += WEIGHT_OF_TREE(occurrences_table[i]);
  227.                     RIGHTPTR_OF_TREE(ptr_fictive_tree)=occurrences_table[i];
  228.                   }
  229.                else RIGHTPTR_OF_TREE(ptr_fictive_tree)=NULL;
  230.                occurrences_table[i]=ptr_fictive_tree;
  231.                (void)qsort((char *)occurrences_table,i+1,sizeof(p_tree),weight_tree_comp);
  232.                if (i)        /* Is there an other node in the occurrence tables? */
  233.                   i++;       /* Yes, then takes care to the fictive node */
  234.              }
  235.      }
  236.   return (*occurrences_table);
  237. }
  238.  
  239. void encode_codes_table(tree,codes_table,code_val)
  240. /* Returned parameters: The data of 'codes_table' can have been modified
  241.    Action: Stores the encoding tree as a binary encoding table to speed up the access.
  242.    'val_code' gives the encoding for the current node of the tree
  243.    Errors: None
  244. */
  245. p_tree tree;
  246. t_bin_val codes_table[257],
  247.           *code_val;
  248. { register unsigned int i;
  249.   t_bin_val tmp_code_val;
  250.  
  251.   if (BYTE_OF_TREE(tree)==257)
  252.      { if (LEFTPTR_OF_TREE(tree)!=NULL)
  253.                              /* The sub-trees on left begin with an bit set to 1 */
  254.           { tmp_code_val = *code_val;
  255.             for (i=31;i>0;i--)
  256.                 BITS_BIN_VAL(*code_val)[i]=(BITS_BIN_VAL(*code_val)[i] << 1)|(BITS_BIN_VAL(*code_val)[i-1] >> 7);
  257.             *BITS_BIN_VAL(*code_val)=(*BITS_BIN_VAL(*code_val) << 1) | 1;
  258.             BITS_NB_BIN_VAL(*code_val)++;
  259.             encode_codes_table(LEFTPTR_OF_TREE(tree),codes_table,code_val);
  260.             *code_val = tmp_code_val;
  261.           };
  262.        if (RIGHTPTR_OF_TREE(tree)!=NULL)
  263.                              /* The sub-trees on right begin with an bit set to 0 */
  264.           { tmp_code_val = *code_val;
  265.             for (i=31;i>0;i--)
  266.                 BITS_BIN_VAL(*code_val)[i]=(BITS_BIN_VAL(*code_val)[i] << 1)|(BITS_BIN_VAL(*code_val)[i-1] >> 7);
  267.             *BITS_BIN_VAL(*code_val) <<= 1;
  268.             BITS_NB_BIN_VAL(*code_val)++;
  269.             encode_codes_table(RIGHTPTR_OF_TREE(tree),codes_table,code_val);
  270.             *code_val = tmp_code_val;
  271.           };
  272.      }
  273.   else codes_table[BYTE_OF_TREE(tree)] = *code_val;
  274. }
  275.  
  276. void create_codes_table(tree,codes_table)
  277. /* Returned parameters: The data in 'codes_table' will be modified
  278.    Action: Stores the encoding tree as a binary encoding table to speed up the access by calling encode_codes_table
  279.    Errors: None
  280. */
  281. p_tree tree;
  282. t_bin_val codes_table[257];
  283. { register unsigned int i;
  284.   t_bin_val code_val;
  285.  
  286.   (void)memset((char *)&code_val,0,sizeof(code_val));
  287.   (void)memset((char *)codes_table,0,257*sizeof(*codes_table));
  288.   encode_codes_table(tree,codes_table,&code_val);
  289. }
  290.  
  291. void huffmanencoding()
  292. /* Returned parameters: None
  293.    Action: Compresses with Huffman method all bytes read by the function 'read_byte'
  294.    Errors: An input/output error could disturb the running of the program
  295. */
  296. { p_tree tree;
  297.   t_bin_val encoding_table[257];
  298.   unsigned char byte_read;
  299.  
  300.   if (!end_of_data())
  301.                              /* Generates only whether there are data */
  302.      { tree=build_tree_encoding();
  303.                              /* Creation of the best adapted tree */
  304.        create_codes_table(tree,encoding_table);
  305.        suppress_tree(tree);
  306.                              /* Obtains the binary encoding in an array to speed up the accesses */
  307.        write_header(encoding_table);
  308.                              /* Writes the defintion of the encoding */
  309.        beginning_of_data();  /* Real compression of the data */
  310.        while (!end_of_data())
  311.              { byte_read=read_byte();
  312.                write_bin_val(encoding_table[byte_read]);
  313.              }
  314.        write_bin_val(encoding_table[256]);
  315.                              /* Code of the end of encoding */
  316.        fill_encoding();
  317.                              /* Fills the last byte before closing file, if any */
  318.      }
  319. }
  320.  
  321. void help()
  322. /* Returned parameters: None
  323.    Action: Displays the help of the program and then stops its running
  324.    Errors: None
  325. */
  326. { printf("This utility enables you to compress a file by using Huffman method\n");
  327.   printf("as given in 'La Video et Les Imprimantes sur PC'\n");
  328.   printf("\nUse: codhuff source target\n");
  329.   printf("source: Name of the file to compress\n");
  330.   printf("target: Name of the compressed file\n");
  331. }
  332.  
  333. int main(argc,argv)
  334. /* Returned parameters: Returns an error code (0=None)
  335.    Action: Main procedure
  336.    Errors: Detected, handled and an error code is returned, if any
  337. */
  338. int argc;
  339. char *argv[];
  340. { if (argc!=3)
  341.      { help();
  342.        exit(BAD_ARGUMENT);
  343.      }
  344.   else if ((source_file=fopen(argv[1],"rb"))==NULL)
  345.           { help();
  346.             exit(BAD_FILE_NAME);
  347.           }
  348.        else if ((dest_file=fopen(argv[2],"wb"))==NULL)
  349.                { help();
  350.                  exit(BAD_FILE_NAME);
  351.                }
  352.             else { huffmanencoding();
  353.                    fclose(source_file);
  354.                    fclose(dest_file);
  355.                  }
  356.   printf("Execution of codhuff completed.\n");
  357.   return (NO_ERROR);
  358. }
  359.